package leetcode.动态规划.middle;

/**
 * @author wangmaolin1
 * @date 2023/11/15 23:25
 */
public class _45 {
    /**
     * 给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
     *
     * 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
     *
     * 0 <= j <= nums[i]
     * i + j < n
     * 返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
     *
     * 输入: nums = [2,3,1,1,4]
     * 输出: 2
     * dp[0]=0
     * dp[1]=Math.min(dp[0]+i> i ? dp[0]+1:
     */
    public  static  int jump(int[] nums) {
        int[]dp=new int[nums.length];
        dp[0] = 0;
        //1,2,1,1,1
        for (int i = 1; i < nums.length; i++) {
            int max=0;
            int j;
            for ( j = 0; j <i; j++) {
                if (nums[j]>max){
                    max=nums[j];
                }
            }
            dp[i]= dp[j]+1;
        }
        return dp[nums.length-1];
    }

    public static void main(String[] args) {
        jump(new int[]{1,2,1,1,1});
    }
}
